#include<iostream>
using namespace std;
class rat
{public:
	rat(double rate)
		:_rate(rate)
	{
	    

	}
    double operator()(double money,int year)
	{
	    return _rate * money * year;
	}





private:
	double _rate;



};
int main()
{
	double rate = 1.1;
	rat st(rate);
	  st(10000, 2);



	  auto ret = [=](double money, int year)
	  {
		  return rate * money * year;
	 
	  };

  
	  ret(10000, 2);


}
class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size();
        int n = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int>arr(m + n);
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {

                arr[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }


        }

        for (int i = 0; i < m + n; i++)
        {
            cout << arr[i] << " ";

        }
        cout << endl;
        // return " ";
        int ret = 0;
        string str;
        for (int i = 0; i < m + n; i++)
        {

            ret += arr[i];
            str.push_back((ret % 10) + '0');
            ret /= 10;

        }
        cout << str << endl;
        while (str.size() > 1 && str.back() == '0')
            str.pop_back();

        reverse(str.begin(), str.end());
        return str;

    }
};/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    template <class T>
    struct fun {

        bool operator()(T x1, T x2)
        {

            return x1->val > x2->val;





        }





    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, fun<ListNode*>>st;
        for (int i = 0; i < lists.size(); i++)
        {
            while (lists[i] != nullptr)
            {
                st.push(lists[i]);
                lists[i] = lists[i]->next;
            }
        }

        ListNode* newhead = new  ListNode(-1);
        ListNode* tail = newhead;
        while (!st.empty())
        {
            ListNode* top = st.top();
            st.pop();
            tail->next = top;
            tail = tail->next;

        }
        tail->next = nullptr;
        return newhead->next;


    }
}; }; #include<iostream>
using namespace std;
int n, m;
int fun()
{
    int x = n;
    for (int i = 0; i < m - 1; i++)
    {
        x *= (n - 1);
        x %= 109;

    }


    return x;



}
int main()
{

    cin >> n >> m;
    cout << fun() << endl;

}#include <iostream>
#include<queue>
#include<cstring>
using namespace std;
char arr[1010][1010];

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int vis[1010][1010];
int x1, y1, x2, y2;
int n, m;
int dfs() {
    queue<pair<int, int>>st;
    memset(vis, -1, sizeof vis);
    if (arr[x2][y2] == '*')return -1;
    st.push({ x1, y1 });
    vis[x1][y1] = 0;
    while (st.size()) {
        auto [a, b] = st.front();
        st.pop();
        for (int i = 0; i < 4; i++) {
            int newx = a + dx[i];
            int newy = b + dy[i];
            if (newx >= 1 && newx <= n && newy >= 1 && newy <= m &&
                arr[newx][newy] == '.' && vis[newx][newy] == -1) {
                st.push({ newx, newy });
                vis[newx][newy] = vis[a][b] + 1;
                if (newx == x2 && newy == y2) {
                    return vis[newx][newy];

                }




            }
        }
    }
    return 0;
}







int main()
{

    cin >> n >> m;

    cin >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    cout << dfs() << endl;

}class Solution {
public:

    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        priority_queue<int, vector<int>, greater<int>>st;
        sort(startEnd.begin(), startEnd.end());
        st.push(startEnd[0][1]);
        for (int i = 1; i < n; i++)
        {

            if (startEnd[i][0] >= st.top())
            {
                st.pop();
                st.push(startEnd[i][1]);





            }
            else {
                st.push(startEnd[i][1]);
            }
        }



        return st.size();

    }
};